#include<bits/stdc++.h>
using namespace std;
namespace IO{
    const int BUF=1<<21;
    char buff[BUF],*p1=buff,*p2=buff;
    #define getchar() (p1==p2&&(p2=((p1=buff)+fread(buff,1,BUF,stdin)),p1==p2)?EOF:*p1++)
    template<typename T>inline void read(T &x){
        char ch=getchar();x=0;int f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x*=f;
    }
    char obuf[BUF],*p3=obuf;
    inline void pc(char ch){
        if(p3-obuf<BUF) *p3++=ch;
        else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;
    }
    inline void put(const int *s){while(*s) pc(*s),++s;}
    char ch[32],ctop;
    template<typename T>inline void print(T x){
    	if(x<0) x=~x+1,pc('-');
        if(!x) return pc(48);
        while(x) ch[++ctop]=x%10^48,x/=10;
        while(ctop) pc(ch[ctop--]);
    }
    inline void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
const int N=1e4+5,mod=111121;
int n,a[N],ans,sum;
vector<int> G[N];
inline int pw(int x,int y){
	if(!x) return 0;
	int ans=1;
	for(;y;y>>=1,x=1ll*x*x%mod)
		if(y&1) ans=1ll*ans*x%mod;
	return ans;
}
void dfs(int p,int fa,int v1,int v2){
	v1&=a[p],v2|=a[p];
	if(!v1) return;
	if(fa) ans=(ans+pw(v1,v2))%mod;
	for(int v:G[p])
		if(v^fa) dfs(v,p,v1,v2);
}
int main(){
	freopen("abstract.in","r",stdin);
	freopen("abstract.out","w",stdout);
	read(n);
	for(int i=1;i<=n;++i) read(a[i]);
	for(int i=1,u,v;i<n;++i){
		read(u),read(v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1;i<=n;++i) dfs(i,0,(1<<30)-1,0);
	ans=55561ll*ans%mod;
	for(int i=1;i<=n;++i) ans=(ans+pw(a[i],a[i]))%mod;
	printf("%d\n",ans);
	return 0;
}

